package com.mlamp.回溯;

import java.util.*;
import java.util.stream.Collectors;

public class 组合总数II {


    public Set<List<Integer>> res = new HashSet<>();

    public static void main(String[] args) {

        组合总数II instance = new 组合总数II();
        //int[] given = new int[]{10,1,2,7,6,1,5};
        int[] given = new int[]{2, 5, 2, 1, 2};
        List<List<Integer>> lists = instance.combinationSum2(given, 5);
        for (List<Integer> item : lists) {
            System.out.println(Arrays.toString(item.toArray()));
        }
    }


    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        LinkedList<Integer> trace = new LinkedList<>();
        core(candidates, target, trace);
        return res.stream().collect(Collectors.toList());
    }

    public void core(int[] candidates, int target, LinkedList<Integer> trace) {
        if (sum(trace, candidates) == target) {
            ArrayList<Integer> integers = new ArrayList<>(trace.stream().map(idx -> candidates[idx]).collect(Collectors.toList()));
            integers.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1 - o2;
                }
            });
            res.add(integers);
            return;
        }

        for (int i = 0; i < candidates.length; i++) {
            if (trace.contains(i)) continue;
            trace.add(i);
            core(candidates, target, trace);
            trace.removeLast();
        }
    }


    public int sum(LinkedList<Integer> res, int[] candidates) {
        int sum = 0;
        for (Integer item : res) {
            sum += candidates[item];
        }
        return sum;
    }
}
